Stochastic Gradient Descent(SGD, 확률적 경사 하강법)

전체 데이터를 사용하기 보다는, 랜덤하게 추출한 데이터 하나만을 사용.

랜덤한 데이터를 사용하는 만큼 noisy해지고, 불안정해 보일 수 있으나, 빠른 속도로 최적 해에 근사한 값을 찾아낼 수 있다.

Assume $L (θ) = \sum_{i = 1}^{n} L_{n} (θ)$ , $L_{n} (θ)$ is data points.
Gradient update : $θ_{k + 1} = θ_{k} - γ_{k} \nabla L (θ_{k})^{⊤} = θ_{k + 1} = θ_{k} - γ_{k} \sum_{n = 1}^{N} \nabla L_{n} (θ_{k})^{⊤}$ : Batch gradient ( for entire $N$ )

장점

random하게 데이터를 추출하므로, local minimum을 도달하는데 있어 여러 convex를 건너띄므로(noisy해짐을 의미) local minimum에 갇힐 확률이 줄어들고 더 좋은 local minimum을 찾을 가능성이 늘어난다.

특정 데이터만을 추출해 사용하므로, 진행하는 방향(gradient)가 Loss function에 대한 local minimum에 대한 방향이 아닌, 무작위한 방향이 될 가능성이 생기므로 local mininum에 갇힐 확률이 줄어든다.

즉, 이는 일반화 성능이 늘어남을 의미한다.
이 뿐만 아니라, 기존의 Gradient Descent와 달리 모든 데이터에 대한 Loss의 평균이 아닌, 데이터의 일부분 만을 update에 사용하므로 계산량이 적다.
또한, 개별 데이터에 대해 수행하므로, 각각의 데이터에 대한 병렬 처리가 가능하다.

보통, Weights는 초기에 작은 값으로 설정한다.
만약 Sigmoid function에 대한 Gradient Descent을 진행하는 것이었다면 0에 가까운 값일 수록 Sigmoid의 도함수의 값이 커지므로, 초반에는 빠르게 수렴하다가 점차 작게 정확하게 local minimum에 도달하게 된다. 500

Learning rate scheduling(simulated annealing): 보통 Learning Rate를 서서히 줄이는 방식으로 진행된다. 초반에는 빠르게 여러 local minimum을 찾다가, 적절한 local minimum에서 수렴하도록 Learning Rate를 줄인다.
허나 여전히 많은 횟수로 local minumum을 탐색해야 하므로, 계산량이 여전히 많이 존재하게 된다.
Randomness인해 local mininum에서 수렴하지 않고 진동한다.

Learning rate scheduling(Learning Rate Decay)

Learning rate를 줄여나가면서, local minimum내에서 과하게 움직이지 않도록 하여 fluctation을 방지할 수 있다.

Linear Decay: $η^{t} = η^{0} (1 - t / T)$ : 선형적으로 줄어든다.
Exponential Decay: $η^{t} = η^{0} exp (- a t)$ : 시간이 지날수록 더 작게 줄어들게 된다. : when $t$ is time index.

Mini-batch SGD

기존의 Gradient Descent와 SGD를 절충시킨 방법.

SGD와 동일하게 진행하되, 데이터 하나 씩이 아니라 작은 개수의 mini-batch에 각각에 대해서 Gradient Descent를 수행한다. mini-batch는 SGD처럼 Random하게 뽑는다.

Mini-batch size는 일종의 hyper parameter가 된다.
커질수록 병렬성이 늘어나지만, randomness와 fluctation이 감소한다.

동일하게, iteration을 돌 때마다 Learning rate scheduling(여기서는 mini-batch size를 변하게 함)을 통해 어느 정도 fluctuation을 해결 가능하다.